package leetcode.bit;

import java.util.Arrays;

/**
 * @author wangmaolin1
 * @date 2023/8/6 17:12
 */
public class _260只出现一次的数字3 {
    /**
     * 给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
     * <p>
     * 你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
     */
    public static int[] singleNumber(int[] nums) {
        //xor = x1^x2
        /*
            解释：
            x1^0=x1;
            x1^x1=0;
            x1^x2^x3= x3^x2^x1=x2^x3^x1

            所以nums所有元素的异或结果，就是不重复的两个数字的异或结果，重复的数字都被异或为0了
         */
        int xor = 0;
        for (int i = 0; i < nums.length; i++) {
            xor ^= nums[i];
        }
        /*
            1.取xor最低位的1，假设是第n位为1，不重复的两个数字为x1和x2，则x1和x2的第n位一定是一个为0一个为1；否则异或后不可能为1
            2.则对于nums中的任意一个元素，根据第n位是否为1，可分为两组，且重复数字的两个元素一定分到相同的组
            3.所以可以对x1和x2两组数据分别异或，最终得到的结果就是x1和x2两个不重复的数字
         */
        // 000001000
        int mx = xor & -xor;

        int x1 = 0, x2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & mx) == 0) {
                x1 ^= nums[i];
            } else {
                x2 ^= nums[i];
            }
        }
        return new int[]{x1, x2};


    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(singleNumber(new int[]{1, 2, 1, 3, 2, 5})));
        System.out.println(1 ^ 2);
    }
}
